#include "seq-list.cpp"

/***
 * 堆排序
 * 基本思路: 利用堆数据结构设计的排序算法, 是一种选择排序
 * 实现过程: 
 *  将无序序列建成一个堆(一般升序采用大顶堆, 降序采用小顶堆)
 *  将堆顶元素与末尾元素进行交换, 将最大元素下沉至末端
 *  重新调整结构使其满足堆定义, 继续2, 直到整个序列有序
 * 时间复杂度: 平均O(nlogn) 最好O(nlogn) 最坏O(nlogn)
 * 空间复杂度: O(1)
 * 稳定性: 不稳定
 * */

// 返回i的左孩子下标
int leftChild(int i)
{
    return 2 * i + 1;
}

// 调整大顶堆 重新有序
void percDown(SqList &L, int i, int n)
{
    int temp, child;
    for (temp = L.data[i]; leftChild(i) < n; i = child) {
        child = leftChild(i);
        if (child != n-1 && L.data[child + 1] > L.data[child])
            child++;
        if (temp < L.data[child])
            L.data[i] = L.data[child];
        else
            break;
    }
    L.data[i] = temp;
}

void sort(SqList &L)
{
    // 构建大顶堆
    for (int i = L.length / 2; i >= 0; i--)
        percDown(L, i, L.length);
    for (int i = L.length - 1; i > 0; i--)
    {
        swap(L, 0, i);
        percDown(L, 0, i);
    }
}

int main(int argc, char const *argv[])
{
    SqList L;
    int data[6] = {6, 5, 3, 2, 7, 1};
    L.data = data;
    L.length = 6;
    printList(L);
    sort(L);
    printList(L);
    return 0;
}
